85. Maximal Rectangle - LeetCode Solution

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        def MHA(heights):
            if len(heights) == 0:
                return 0

            stack = []

            left = []
            right = []

            for i in range(len(heights)):

                while len(stack) != 0 and heights[stack[-1]] >= heights[i]:
                    stack.pop()

                if len(stack) == 0:
                    left.append(0)
                else:
                    left.append(stack[-1] + 1)

                stack.append(i)

            stack = []

            for i in range(len(heights) - 1, -1, -1):
                while len(stack) != 0 and heights[stack[-1]] >= heights[i]:
                    stack.pop()

                if len(stack) == 0:
                    right.append(len(heights) - 1)
                else:
                    right.append(stack[-1] - 1)

                stack.append(i)

            right = right[::-1]


            ans = []

            for i in range(len(right)):
                ans.append((right[i] - left[i] + 1) * heights[i])

            return max(ans)
        
        
        if len(matrix) == 0:
            return 0
        area = []


        x = [0] * len(matrix[0])


        for i in range(len(matrix)):

            for j in range(len(matrix[i])):
                if int(matrix[i][j]) == 0:
                    x[j] = 0
                else:
                    x[j] += int(matrix[i][j])


            area.append(MHA(x))


        print(max(area))
        return max(area)